/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
 var minDistance = function(word1, word2) {
  // dp[i][j] 表示以i-1位结尾的字符串和以j-1为结尾的字符串要保持一致需要的操作数
  let dp = new Array(word1.length+1).fill(0).map(()=>new Array(word2.length+1).fill(0))
  // 初始化 dp[i][0] 和dp[j][0] 表示一个字符串和一个空串要多少操作才能相等 例如 2-1 表示下标为1的字符串要操作两步 就是dp[i][0] = i
  for(let i = 0;i <= word1.length;i++){
    dp[i][0] = i
  }
  for(let i = 0;i <= word2.length;i++){
      dp[0][i] = i
  }
  for(let i = 1;i <= word1.length;i++){
    for(let j = 1;j <= word2.length;j++){
      if(word1[i-1] === word2[j-1]){
        dp[i][j] = dp[i-1][j-1] // 如果i-1和j-1位置的两个数相同 name此时的操作和前一步的操作key相同 就是不需要再增删该了
      }else{
        // 如果不相同就需要增删改了
        // 其中正价和删除的操作数都是相等的 可以简化为都是删除
        // 删除 
        // 这两个数不相同 可以删除掉i-1 也可以删除掉j-1 删除掉i-1 就是dp[i-1][j]+1 删除掉j-1就是dp[i][j-1]+1
        // 修改
        // 如果两个数字不相同 修改其中的一个数字 就是相当于以i-2,j-2位结尾的数字的操作值增加一步操作就可以了 dp[i-1][j-1]+1
        // 这几种情况中取最小值
        dp[i][j] = Math.min(dp[i-1][j-1]+1,dp[i-1][j]+1,dp[i][j-1]+1)
      }
    }
  }
  console.log(dp)
  return dp[word1.length][word2.length] // 最后返回以各自最后一个元素结尾的操作数
};